package com.shiguiwu.springmybatis.algorithm.stack;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @description: 中缀表达式转后缀
 * <p>
 * <p>
 * 1,初始化两个栈：运算符栈s1和储存中间结果的栈s2；
 * 2,从左至右扫描中缀表达式；
 * 3,遇到操作数时，将其压s2
 * 4,遇到运算符时，比较其与s1栈顶运算符的优先级：
 * (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
 * (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
 * (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4、(1)步骤)与s1中新的栈顶运算符相比较；
 * 遇到括号时：
 * 5,(1) 如果是左括号“(”，则直接压入s1
 * (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
 * 6,重复步骤2至5，直到表达式的最右边
 * 7,将s1中剩余的运算符依次弹出并压入s2
 * 8,依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
 * @author: stone
 * @date: Created by 2022/11/20 16:11
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.stack
 */
@Slf4j
public class PolandNotation {

    public static String LEFT_BRACKET = "(";

    public static String RIGHT_BRACKET = ")";

    public static Pattern PATTERN = Pattern.compile("\\d+");

    //、1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
    public static void main(String[] args) {
        midExp2Suffix("1+((2+3)×4)-5");

        log.info("符号为 ===> {},{}",String.valueOf('0'),"0");
    }


    public static void midExp2Suffix(String express) {

        List<String> collect = new ArrayList<>();
        char[] chars = express.toCharArray();
        for (char aChar : chars) {
            collect.add(String.valueOf(aChar));
        }



        //初始化两个栈，由于s2栈只有push方法，优化为list
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>(chars.length);

        for (String item : collect) {
            if (PATTERN.matcher(item).matches()) {
                s2.add(item);
            }
            //遇到左括号，压栈
            else if (LEFT_BRACKET.equals(item)) {
                s1.push(item);
            }

            //遇到右括号
            else if (RIGHT_BRACKET.equals(item)) {
                //依次出栈，直到左括号为止
                while (!LEFT_BRACKET.equals(s1.peek())) {
                    s2.add(s1.pop());
                }

                //弹出左括号为止
                s1.pop();
            }

            //最后约到操作符
            else {

                //优先级不高栈顶的符号
                while (s1.size() != 0 && !Operation.comparor(item, s1.peek())) {
                    s2.add(s1.pop());
                }
                    //最后再压栈
                s1.push(item);



            }
        }

        if (s1.size() != 0) {
            s2.add(s1.pop());
        }


        log.info("打印结果 ===> {}", s2);
    }


    /**
     * 优先级操作类
     */
    static class Operation {
        public static Integer ADD = 1;
        public static Integer SUB = 1;
        public static Integer MUL = 4;
        public static Integer DIV = 4;

        public static boolean comparor(String x, String y) {

            return getVal(x) > getVal(y);
        }

        public static Integer getVal(String exp) {
            int res = 0;
            switch (exp) {
                case "+":
                    res = ADD;
                    break;
                case "-":
                    res = SUB;
                    break;

                case "×":
                    res = MUL;
                    break;
                case "/":
                    res = DIV;
                    break;
                default:
                    log.error("不支持此符号 ===> {}", exp);
            }
            return res;
        }


    }
}
